//https://leetcode.cn/problems/combination-sum/?envType=daily-question&envId=2024-04-20https://leetcode.cn/problems/combination-sum/?envType=daily-question&envId=2024-04-20

class Solution {
	vector<vector<int>>res;
	vector<int>tmp;
public:
	void dfs(vector<int>& candidates, int i, int sum, int target) {
		if (i >= candidates.size() || sum > target) {
			return;
		}
		else if (sum == target) {
			res.push_back(tmp);
		}
		else {
			for (int j = i; j < candidates.size(); j++) {
				if (candidates[j] <= target) {
					tmp.push_back(candidates[j]);
					dfs(candidates, j, sum + candidates[j], target);
					tmp.pop_back();
				}
			}
		}
	}
	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		dfs(candidates, 0, 0, target);
		return res;
	}
};